import java.util.*;

public class Solution45 {

    public int jump(int[] nums) {
        int target = nums.length-1;
        int tmpLoc = 0;
        int step = 0;
        while(tmpLoc < target){
            int maxStep = nums[tmpLoc];
            int nextLoc = 0;
            int nextMax = 0;
            for (int i = 1; i <= maxStep; i++) {
                int loc = tmpLoc+i;
                if(loc >= target){
                    nextLoc = target;
                    break;
                }
                if(nextMax < nums[loc]+loc){
                    nextMax = nums[loc]+loc;
                    nextLoc = loc;
                }
            }
            tmpLoc = nextLoc;
            step++;
        }
        return step;
    }

    public static void main(String[] args) {
        Solution45 s = new Solution45();
        System.out.println(s.jump(new int[]{2,3,1}));
    }
}
